题解 P1613 【跑路】

发表于 | 更新于

$Description$

有$n$个点，$m$条边，边权为一，每次都可以走$2^k$条边，问最多要走几次

$Solution$

考虑倍增，设$f_{i,j,k}$表示$i$到$j$是否能以走$2^k$条边相互到达。

可以用$Floyd$的方法求出$f$数组。

求完后，若$f_{i,j,k}=1(0\leqslant k\leqslant 64)$,则连一条$i$到$j$的边权为$1$的边

最后再用$Floyd$求出$1$~$n$的最短路即可。

$Code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
#define ll long long
#define re register
#define inf 0x3f3f3f3f
#define N 100
using namespace std;
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
int d[N][N],f[N][N][N];
signed main(){
    int n=read(),m=read();
    memset(d,0x3f,sizeof(d));
    for (int i=1;i<=m;++i){
        int u=read(),v=read();
        f[u][v][0]=1;d[u][v]=1;
    }
    for (int p=1;p<=64;++p)
        for (int k=1;k<=n;++k)
            for (int i=1;i<=n;++i)
                for (int j=1;j<=n;++j)
                    if (f[i][k][p-1]&f[k][j][p-1])
                        f[i][j][p]=1,d[i][j]=1;
    for (int k=1;k<=n;++k)
        for (int i=1;i<=n;++i)
            for (int j=1;j<=n;++j)
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    cout<<d[1][n]<<endl;
    return 0;
}